package fun.coding.leetcode;

import java.util.LinkedList;
import java.util.Queue;

public class PopulatingNextRightPointersInEachNode {

	public static void main(String[] args) {
		PopulatingNextRightPointersInEachNode p = new PopulatingNextRightPointersInEachNode();
		
		/*
		 *        1
		 *     2     3
		 *  
		 */
		TreeLinkNode root = new TreeLinkNode(1);
		root.left = new TreeLinkNode(2);
		root.right = new TreeLinkNode(3);
		
		p.connectOneQueue(root);
	}

	// An iterative solution only uses O(1) constant space
	// The idea is while connecting current level, connect the next level
	public void connect(TreeLinkNode root) {
		if (root == null) return;
		
		TreeLinkNode cur = root;
		TreeLinkNode nextLevel = root.left;
		while (cur != null && nextLevel != null) {
			while (cur != null) {
				cur.left.next = cur.right;
				cur.right.next = cur.next == null ? null : cur.next.left;
				cur = cur.next;
			}
			cur = nextLevel;
			nextLevel = nextLevel.left;
		}
	}
	
	/*
	 *        	  1
	 *     	2      	     3
	 *   4      5     6      7
	 *  8 9   10 11  12 13  14 15  
	 *   
	 *    This is a pre order traversal, first to connect the dot while dfs, 
	 *    recursion uses O(LgN) space [function stack], O(N) time
	 */
	public void connectRecursion(TreeLinkNode root) {
		if (root == null) return;
		
		if (root.left != null) {
			root.left.next = root.right;
		}
		
		if (root.right != null) {
			root.right.next = root.next == null ? null : root.next.left;
		}
		
		connect(root.left);
		connect(root.right);
	}
	
	public void connectOneQueue(TreeLinkNode root) {
		if (root == null) return;
		
		Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();
		q.add(root);
		while (!q.isEmpty()) {
			TreeLinkNode pre = null;
			int size = q.size();
			// Note, for this pattern, cannot use i < q.size() since size is changing within the for loop
			for (int i = 0; i < size; i++) {
				TreeLinkNode t = q.poll();
				
				if (t.left != null) {
					q.add(t.left);
				}
				if (t.right != null) {
					q.add(t.right);
				}
				
				if (pre != null) {
					pre.next = t;
				}
				
				pre = t;
			}
		}
	}
	
	
	// Only comment, Should never use 2 stupid queues for this problem
	public void connectQueue(TreeLinkNode root) {
		if (root == null) return;
		
		Queue<TreeLinkNode> q1 = new LinkedList<TreeLinkNode>();
		Queue<TreeLinkNode> q2 = new LinkedList<TreeLinkNode>();
		
		q1.add(root);
		
		while (true) {
			if (q1.isEmpty()) break;
			
			TreeLinkNode pre = q1.peek();
			
			while (!q1.isEmpty()) {
				TreeLinkNode t = q1.poll();
				pre.next = t;
				pre = t;
				
				if (t.left != null) {
					q2.add(t.left);
				}
				if (t.right != null) {
					q2.add(t.right);
				}
			}
			pre.next = null;
			q1 = q2;
			q2 = new LinkedList<TreeLinkNode>();
		}
		
	}
}
